#ifndef SINGLELIST_
#define SINGLELIST_

#include <iostream>
#include <algorithm>

/*=======================================================================================*/
//*********************************** C L A S S *****************************************
/*=======================================================================================*/
/*---def. Node---*/
template <class parNode>
class SLNode
{
public:
    parNode Info;
    SLNode *pNext;
    SLNode(parNode input, SLNode *ptr=NULL)
    {
        Info = input;
        pNext = ptr;
    }
};

/*---def. Single List---*/
template <class parList>
class SingleList
{
public:
    void addToTail(parList addInfo);
    void addToHead(parList addInfo);
    parList removeFromTail(void);
    parList removeFromHead(void);
    parList removeNode(parList remInfo);
    void reverseList(void);
    bool isEmpty(void);
    bool isInList(parList lookInfo);
    friend std::ostream& operator<<(std::ostream& _stream, SingleList<parList> &_list)
    {
        SLNode<parList> *ptr = _list.pHead;
        for(;ptr!=NULL;)
        {
            _stream<<ptr->Info<<std::endl;
            ptr=ptr->pNext;
        }
        return _stream;
    }
    SingleList(void)
    {
        pHead = '\0';
        pTail = '\0';
    }
    ~SingleList(void);

private:
    SLNode<parList> *pHead;
    SLNode<parList> *pTail;
};

/*=======================================================================================*/
//****************************** I M P L E M E N T A T I O N ****************************
/*=======================================================================================*/
//1. ~SingleList:
template <class parList>
SingleList<parList>::~SingleList(void)
{
    if(false==isEmpty()) //means list is not empty, so must be deletion performed
    {
        SLNode<parList> *ptr = pHead;
        for(;NULL != ptr;)
        {
            ptr = pHead->pNext;
            delete pHead;
            pHead = ptr;
        }
    }
}

//2. isEmpty:
template <class parList>
bool SingleList<parList>::isEmpty(void)
{
    if(NULL == pHead && NULL == pTail) return true; //yes is empty
    else return false;
}

//3. addToTail:
template <class parList>
void SingleList<parList>::addToTail(parList addInfo)
{
    if(true==isEmpty())
    {
        pTail=pHead = new SLNode<parList>(addInfo,NULL);
    }
    else
    {
        pTail=pTail->pNext = new SLNode<parList>(addInfo,NULL);
    }
}

//4. addToHead:
template <class parList>
void SingleList<parList>::addToHead(parList addInfo)
{
    if(true == isEmpty())
    {
        pTail = pHead = new SLNode<parList>(addInfo,NULL);
    }
    else
    {
        SLNode<parList> *ptr;
        ptr = new SLNode<parList>(addInfo,NULL);
        ptr->pNext = pHead;
        pHead = ptr;
    }
}

//5. removeFromTail:
template <class parList>
parList SingleList<parList>::removeFromTail(void)
{
    parList temp_el;
    if(true==isEmpty()) //==0
    {
        throw ("(Err1)Attempt remove element of empty list");
    }
    else
    {
        if(pTail == pHead) //==1
        {
            temp_el = pTail->Info;
            delete pHead;
            pTail = pHead = NULL;
        }
        else //>=2
        {
            SLNode<parList> *ptr;
            for(ptr=pHead; ptr->pNext!=pTail; ptr=ptr->pNext);
            temp_el = pTail->Info;
            delete pTail;
            pTail=ptr;
            pTail->pNext=NULL;
        }
    }
    return temp_el;
}

//6. removeFromHead:
template <class parList>
parList SingleList<parList>::removeFromHead(void)
{
    parList temp_el;
    if(true==isEmpty()) //==0
    {
        throw ("(Err2)Attempt remove element of empty list");
    }
    else
    {
        if(pTail==pHead) //==1
        {
            temp_el = pHead->Info;
            delete pHead;
            pTail=pHead=NULL;
        }
        else //>=2
        {
            temp_el = pHead->Info;
            SLNode<parList> *ptr;
            ptr = pHead->pNext;
            delete pHead;
            pHead=ptr;
        }
    }
    return temp_el;
}

//7. isInList:
template <class parList>
bool SingleList<parList>::isInList(parList lookInfo)
{
    SLNode<parList> *ptr;
    for(ptr = pHead; NULL != ptr; ptr = ptr->pNext)
    {
        if(ptr->Info == lookInfo) return true;
    }
    return false;
}

//8. removeNode:
template <class parList>
parList SingleList<parList>::removeNode(parList remInfo)
{
    parList temp_el;

    if(true == isInList(remInfo) && pTail == pHead) //==1
    {
        temp_el = removeFromHead();
        pTail = pHead = NULL;
    }
    else if(true==isInList(remInfo)) //>=2
    {
        SLNode<parList> *ptr = NULL;
        SLNode<parList> *ptr_shadow = pHead;

        for(ptr=pHead; NULL!=ptr; ptr=ptr->pNext)
        {
            if(ptr->Info == remInfo && ptr == pHead)
            {
                removeFromHead();
                break;
            }
            else if(ptr->Info == remInfo)
            {
                temp_el = ptr->Info;
                ptr_shadow->pNext = ptr->pNext;
                delete ptr;
                break;
            }
            else if(ptr!=pHead)
            {
                ptr_shadow = ptr_shadow->pNext;
            }
        }
    }
    else
    {
        throw ("(Err3)Attempt remove inexistent element of list");
    }
    return temp_el;
}

//9. reverseList:
template <class parList>
void SingleList<parList>::reverseList(void)
{
    SLNode<parList> *ptr1;
    SLNode<parList> *ptr2;
    SLNode<parList> *pBuffer;
    //-------------------------------

    for(ptr2 = ptr1 = pHead; ptr2 != NULL; )
    {
        if(pHead == ptr1)
        {
            std::swap(pHead,pTail);
            pBuffer = pTail->pNext;
            pTail->pNext = NULL;
            ptr2 = pBuffer;
        }
        else
        {
            pBuffer = ptr2->pNext;
            ptr2->pNext = ptr1;
            ptr1 = ptr2;
            ptr2 = pBuffer;
        }
    }
}

#endif//SINGLELIST_
